package cn.edu.besti.cs1723.DZX2304;


import experience.Hashtable;
import week7.jsjf.LinkedBinarySearchTree;

import java.util.Arrays;

import static experience.Hashtable.Hashsearch;

public class Searching<T> {
    public static <T> boolean linearSearch(T[] data, int min, int max, T target) {
        int index = min;
        boolean found = false;

        while (!found && index <= max) {
            found = data[index].equals(target);
            index++;
        }

        return found;
    }



    //二分查找（折半查找），版本1
    public boolean BinarySearch1(Integer a[], int value, int n) {
        int low, high, mid;
        low = 0;
        high = n - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (a[mid] == value) {
                return true;
            }
            if (a[mid] > value) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }

    //二分查找，递归版本
    public int BinarySearch2(int a[], int value, int low, int high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == value) {
            return mid;
        }
        if (a[mid] > value) {
            return BinarySearch2(a, value, low, mid - 1);
        } else {
            return BinarySearch2(a, value, mid + 1, high);
        }
    }

    public static int max_size = 20;//斐波那契数组的长度

    // 构造一个斐波那契数组
    public static void Fibonacci(int[] F) {
        F[0] = 0;
        F[1] = 1;
        for (int i = 2; i < max_size; ++i) {
            F[i] = F[i - 1] + F[i - 2];
        }
    }
    //插值查找递归实现
    public static <T extends Comparable<? super T>> boolean InterpolationSearch(T[] data, int low, int high,T target) {
        boolean found = false;
        int mid = low + (high - low) * (target.compareTo(data[low])) / (data[high].compareTo(data[low]));

        if (target.compareTo(data[mid]) == 0)
            found = true;

        else if (data[mid].compareTo(target) > 0)
        {
            if (low <= mid - 1)
                found = InterpolationSearch(data, low, mid - 1, target);
        }
        else if (mid + 1 <= high)
        {
            found = InterpolationSearch(data, mid + 1, high, target);
        }
        return found;
    }




    //斐波那契查找
    public static <T extends Comparable<? super T>> boolean FibonacciSearch(T[] data, int low, int high, T target) {

        int[] F = new int[max_size];
        Fibonacci(F); //构造一个斐波那契数组F

        int n = high - low + 1;

        int k = 0;
        while (n > F[k] - 1)  // 计算n位于斐波那契数列的位置
        {
            k++;
        }

        T[] temp;   //将数组data扩展到F[k]-1的长度
        temp = Arrays.copyOf(data, F[k] - 1);

        for (int i = n; i < F[k] - 1; ++i) {
            temp[i] = data[n - 1];
        }

        while (low <= high) {
            int mid = low + F[k - 1] - 1;
            if (target.compareTo(temp[mid]) < 0) {
                high = mid - 1;
                k -= 1;
            } else if (target.compareTo(temp[mid]) > 0) {
                low = mid + 1;
                k -= 2;
            } else {
                return true;
            }
        }
        return false;
    }
    // 二叉查找树
    public<T extends Comparable<? super T>> boolean BinarySearchTreeSearch(T[] data, int low, int high, T target)
    {
        boolean found = false;
        LinkedBinarySearchTree linkedBinarySearchTree = new LinkedBinarySearchTree();

        for (int i= low;i<= high;i++) {
            linkedBinarySearchTree.addElement(data[i]);
        }

        while (found == false&&linkedBinarySearchTree.root!=null) {
            if (target.equals(linkedBinarySearchTree.root.getElement())){
                found = true;
            }
            else
            {
                if (target.compareTo((T)linkedBinarySearchTree.root.getElement()) < 0) {
                    linkedBinarySearchTree.root = linkedBinarySearchTree.root.left;
                } else {
                    linkedBinarySearchTree.root = linkedBinarySearchTree.root.getRight();
                }
            }
        }
        return found;
    }

    // 分块查找
    public static <T extends Comparable<? super T>> boolean partitionSearch(T[] data, int min, int max,T target) {
        boolean found = false;
        int partition = partition(data,min,max);
        int leftPartition = partition(data,min,partition-1);
        int rightPartition = partition(data,partition+1,max);

        if (target.compareTo(data[partition]) == 0) {
            found = true;
        } else
        {
            if (target.compareTo(data[partition]) < 0)
            {
                if (target.compareTo(data[leftPartition]) == 0) {
                    found = true;
                } else
                {
                    if (target.compareTo(data[leftPartition]) < 0) {
                        found =  linearSearch(data,min,leftPartition-1,target);
                    } else {
                        found =  linearSearch(data,leftPartition+1,partition-1,target);
                    }
                }
            }
            else
            {
                if (target.compareTo(data[rightPartition]) == 0) {
                    return true;
                } else
                {
                    if (target.compareTo(data[rightPartition]) < 0) {
                        found = linearSearch(data,partition+1,rightPartition-1,target);
                    } else {
                        found = linearSearch(data,rightPartition+1,max,target);
                    }
                }
            }
        }
        return found;
    }
    private static <T extends Comparable<? super T>> void swap(T[] data, int index1, int index2)
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    private static <T extends Comparable<? super T>> int partition(T[] data, int min, int max)
    {
        T partitionelement;
        int left, right;
        int middle = (min + max) / 2;

        //使用中间数据值作为分区元素
        partitionelement = data[middle];
        // 暂时把它移开
        swap(data, middle, min);

        left = min;
        right = max;

        while (left < right)
        {
            // 搜索一个元素，它是>分区元素
            while (left < right && data[left].compareTo(partitionelement) <= 0) {
                left++;
            }

            // 搜索一个元素，它是<分区元素
            while (data[right].compareTo(partitionelement) > 0) {
                right--;
            }

            // 交换元素
            if (left < right) {
                swap(data, left, right);
            }
        }

        // 将分区元素移动到适当的位置
        swap(data, min, right);

        return right;
    }
    public boolean Hashsearching(Integer[]num,Integer num1){

        Hashtable a=new Hashtable();
        a.add(num);
        return Hashsearch(num1);

    }
}
